This invention relates to the field of authentication of electronic data, and more specifically, to producing digital signatures that allow for revokable anonymity and the ability to detect the unauthorized use of a secret key without compromising anonymity requirements.
Electronic commerce (E-Commerce) is one of the fastest growing segments of the Internet. All aspects of monetary transactions are being carried out electronically including banking, investing, purchase and sales, and the like. While the benefits of E-Commerce are many, certain precautions must be taken to prevent abuse and to ensure that the privacy of the participants is not compromised. Accordingly, authentication techniques utilizing xe2x80x9celectronic signaturesxe2x80x9d and xe2x80x9csecret keysxe2x80x9d have been developed so that assurances can be made that the transactions requested are legitimate transactions. Many examples of such techniques can be found in the prior art (see, for example, M. Jakobsson and M. Yung, xe2x80x9cApplying Anti-Trust Policies to Increase Trust in a Versatile E-Money System,xe2x80x9d Advances in Cryptology-Proceedings of Financial Cryptography ""97, pp. 217-238.
In view of the need for protection of privacy, much of the research in the field of E-commerce has been focused on developing payment or signature schemes with revokable anonymity. Such schemes facilitate general anonymity with respect to transactions, but allow details of a particular transaction or user to be identified under appropriate circumstances (e.g., pursuant to a court order). For example, a set of xe2x80x9ctrusteesxe2x80x9d might possess the ability to remove the anonymity of a given user or transaction when all agree that there is reason to believe that the user is committing a crime or that a particular transaction is fraudulent.
xe2x80x9cBlindingxe2x80x9d is a technique utilizing electronic signatures by which the provider of a message for signing, e.g., a bank customer, can transform the message to be signed into a form which obscures the content of the message. Thus, the signer, e.g., a bank, can sign the transformed message and return it to the provider of the message, and the provider can transform the message in such a way that the result retains the digital signature property related to the original message content, but the result is not readily associated with the transformed message received by the signer. One example of such a technique is disclosed in U.S. Pat. No. 4,759,063 to Chaum, incorporated herein by reference.
To understand the known methods of revoking anonymity it is necessary to understand the mechanics of electronic transactions. For example, a typical electronic transaction will involve three participants: a Signer, typically a bank; a Receiver, typically a consumer who is a customer of the Signer; and a Verifier, typically a merchant who transacts business with the Receiver.
For the purpose of this explanation, presume that a Receiver A has $10,000 in an established bank account with a Signer bank B. If Receiver A needs conventional cash, he or she simply goes into the bank or to an automatic teller machine (ATM), makes a withdrawal, and receives the cash in hand. If, however, Receiver A wants to have the ability to conduct electronic transactions, for example, with merchant (Verifier) C, then Receiver A needs to request a withdrawal of electronic cash (E-Coin) so that it will be available for use on demand.
To xe2x80x9cwithdrawxe2x80x9d E-Coin, Receiver A sends a request to the Signer bank B and asks the bank to issue, for example, $2,000 in E-Coin to Receiver A. This request would typically be in the form of an authenticated encrypted e-mail message which allows the bank to confirm the identity of the requester. Signer bank B, after verifying that the funds are available, will issue the E-Coin (electronic funds, essentially an e-mail), encrypted using conventional encryption methods, and bearing a xe2x80x9csignaturexe2x80x9d S which identifies Signer bank B as the issuer of the E-Coin. The signature S is a verification that the bank issued the E-Coin and that it is, therefore, acceptable to use for an electronic transaction.
The Signer bank B keeps daily transcripts, called xe2x80x9csigning transcripts,xe2x80x9d of all E-Coin issued (withdrawn). This transcript is used to correlate withdrawals with the appropriate bank account. It is also used, as discussed below, to verify that E-Coin presented to a merchant/verifier is legitimate.
With the E-Coin now available for immediate spending (in this example, $2,000), Receiver A can present some or all of the E-Coin to Merchant C to transact business. Thus, if Receiver A wants to purchase a $200.00 item from Merchant C, Receiver A will send an electronic purchase request along with an electronic xe2x80x9cdraftxe2x80x9d promising to pay Merchant C $200.00 of E-Coin. The electronic draft includes the signature S issued by the Signer bank B. Merchant C will then deliver the item to Receiver A and, possibly at a later time and/or date, present the electronic draft to the bank for payment.
Signer bank B keeps a second transcript, called herein a xe2x80x9cspent E-Coin transcriptxe2x80x9d, which identifies all E-Coin that has been deposited by a verifier such as a merchant or a payee (if an item is found on this transcript, this indicates that the E-coin identified has been spent). The spent E-Coin transcript gives the bank the ability to track the use of E-Coin by a particular bank customer so that assurances can be made that a particular bank customer has not xe2x80x9coverdrawnxe2x80x9d an account (the E-Coin is somewhat analogous to a checking account). For example, with the spent E-Coin transcript the bank can determine that more cash was spent than was issued to a particular user (an overdraft) and initiate a trace to identify the overspender.
Used in connection with the signing transcript, the spent E-Coin transcript also gives the bank the ability scan for the circulation of counterfeit E-Coin. By comparing the signing transcripts with the spent E-Coin transcripts, the bank can identify the existence of counterfeit E-Coin because there would be instances of the spending of E-Coin seemingly issued by the bank (e.g., bearing the banks electronic signature) but with no record of issuance in the signing transcript.
While the system described allows for recording and tracing of transactions, two basic problems exist. First, the correlation process is computationally costly because each transaction must be xe2x80x9cexaminedxe2x80x9d during the correlation process, which is a time-consuming task. Second, the system provides no anonymity, as the bank has access to complete information about the purchasing habits of its customers, which is unacceptable.
Recently, a technique referred to as xe2x80x9cmagic ink signaturesxe2x80x9d has been developed to offer revokable privacy and a new tracing option. This method is described in detail in xe2x80x9cDistributed Magic Ink Signaturesxe2x80x9d by M. Jakobsson and M. Yung, Advances in Cryptology-Proceedings of Eurocrypt ""97, pp. 450-464. According to this technique, the Signer bank B distributes the responsibility of both signing, tracing, and maintenance of detection mechanisms (e.g., the keeping of transcripts) among a subset of smaller xe2x80x9cbanksxe2x80x9d (e.g., several isolated computer systems, several different offices of the bank, a government organization, or a combination thereof), so that no single unit has a complete record of a transaction, but instead several of the smaller banks must collaborate (i.e., a quorum is required) to trace the transaction. Only after it has been determined that an invalid signature has been obtained (or an overdraft has occurred) are the subset of smaller banks given the authority to collaborate to revoke the anonymity and identify the transaction or Receiver.
The above-described magic ink technique allows a tighter control over tracing by allowing suspicions to be verified without divulging any specific information about the signer, receiver, or verifier. Using the magic ink technique, three tracing options are available, namely (1) by tracing the identity of the spender from a particular unit of E-Coin; (2) by tracing a particular unit of E-Coin from the identity of a spender; or (3) by comparing one particular unit of E-Coin with the identity of one particular holder of E-Coin issued by the bank. Tracing options (2) and (3) have computational costs that are independent of the number of signatures that have been generated; thus they can be accomplished efficiently. However, tracing option (1), tracing the identity of a spender from a particular unit of E-Coin, has an expected computational cost which is linear in relation to the number of generated signatures. This relationship between the number of signatures and the cost of tracing raises a significant practical concern, since tracing option (1) is likely to be the most commonly-used technique, given that this technique allows the tracing of overspent funds. Thus, it would be beneficial to be able to accomplish revokable anonymity with traceability by tracing option (1) in a manner in which the computational cost of doing the trace is less than linear with respect to the number of issued signatures.
Another benefit of the prior art magic ink signatures technique compared to other schemes with revokable anonymity is that it allows the signer/bank to distinguish between valid signatures that were produced by the bank servers, and valid signatures that were produced by another party holding the signing keys. This is important if there is a suspicion that the signing keys of the banks have been corrupted by, for example, an attacker obtaining the Signer bank""s secret key, enabling the attacker to create untraceable counterfeit E-Coin (called a xe2x80x9cbank robbery attackxe2x80x9d in the literature). While the magic ink signature technique can act as a definitive deterrent against attacks aiming to corrupt the bank keys, the very high cost of the filtering makes the method impractical unless it is certain that the signing keys have been corrupted, i.e., it is only practical to use the method for confirmation and/or correction of the problem after it occurs rather than for early detection of the problem.
The present invention is an improvement upon the magic ink signature scheme. According to the present invention, when a Receiver makes a request m to a Signer (e.g., a bank customer asks the bank to issue E-Coin), the Receiver includes a xe2x80x9chint generation valuexe2x80x9d me. The hint generation value me is essentially an encrypted version of the request m. It is simultaneously decrypted and blinded by the Signer and is stored on the signing transcript as a hint value mh.
When a merchant/Verifier transmits deposit signatures corresponding to spent E-Coin to be deposited, the transmitted deposit signature, which includes the encrypted request m (and which is, therefore, equivalent to the hint generation value me), is decrypted and blinded by the bank in the same manner as was the hint generation value me. Thus, the encrypted incoming deposit signature from the merchant/Verifier should include a value that matches the hint value stored on the signing transcript, confirming that the E-Coin is valid without revealing any identifying information about who spent the E-Coin, i.e., anonymity is preserved. If the incoming deposit signature does not contain a value that matches a hint value in the signing transcript, the bank immediately knows that counterfeit E-Coin is being circulated and can take the steps necessary to stop any further illicit transactions and attempt to identify the source of the corruption. Further, since the incoming encrypted deposit signature will contain a value that matches the hint value on the signing transcripts in the case of a valid transaction, tracing time (e.g., for tracing of overdrafts) is significantly reduced because the hint value will identify the location of the appropriate record in the transcript and thus an exhaustive, item-by-item search of the transcript is avoided.